# 528. 按权重随机选择
import bisect
import random
from typing import List


class Solution:

    def __init__(self, w: List[int]):
        probability = [0] * len(w)
        _sum = sum(w)
        cur = 0
        for i in range(len(w)):
            cur += w[i]
            probability[i] = cur / _sum
        self.probability = probability

    def pickIndex(self) -> int:
        return bisect.bisect_right(self.probability, random.random())


if __name__ == '__main__':
    a = [1, 2, 2.5, 3, 4]
    idx = bisect.bisect(a, 1)
    print(idx)
